<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>


<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">



  <meta name="description" content="痛苦的数据结构OJ"/>




  <meta name="keywords" content="c++, 算法, OJ, 八一" />



  <meta name="baidu-site-verification" content="HhUstaSjr0" />



  <meta name="google-site-verification" content="UA-102975942-1" />






  <link rel="alternate" href="/atom.xml" title="八一">




  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=2.6.0" />



<link rel="canonical" href="https://bay1.top/2017/05/17/痛苦的数据结构OJ/"/>


<link rel="stylesheet" type="text/css" href="/css/style.css?v=2.6.0" />
<link rel="stylesheet" type="text/css" href="/css/prettify.css" media="screen" />
<link rel="stylesheet" type="text/css" href="/css/sons-of-obsidian.css" media="screen" />



  <link rel="stylesheet" type="text/css" href="/lib/fancybox/jquery.fancybox.css" />




  
  <script id="baidu_analytics">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?9a885cc9fb6cd7bcef579deb8efe8a70";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>



  <script id="google_analytics">
    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

        ga('create', 'UA-102975942-1', 'auto');
        ga('send', 'pageview');
  </script>










    <title> 痛苦的数据结构OJ - 八一 </title>
  </head>

  <body><div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/." class="logo">八一</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>

<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    
      <a href="/archives">
        <li class="mobile-menu-item">
          
          
            文章
          
        </li>
      </a>
    
      <a href="/tags">
        <li class="mobile-menu-item">
          
          
            标签
          
        </li>
      </a>
    
      <a href="/about">
        <li class="mobile-menu-item">
          
          
            关于/友链
          
        </li>
      </a>
    
      <a href="/search">
        <li class="mobile-menu-item">
          
          
            站内搜索
          
        </li>
      </a>
    
  </ul>
</nav>

    <div class="container" id="mobile-panel">
      <header id="header" class="header"><div class="logo-wrapper">
  <a href="/." class="logo">八一</a>
</div>

<nav class="site-navbar">
  
    <ul id="menu" class="menu">
      
        <li class="menu-item">
          <a class="menu-item-link" href="/archives">
            
            
              文章
            
          </a>
        </li>
      
        <li class="menu-item">
          <a class="menu-item-link" href="/tags">
            
            
              标签
            
          </a>
        </li>
      
        <li class="menu-item">
          <a class="menu-item-link" href="/about">
            
            
              关于/友链
            
          </a>
        </li>
      
        <li class="menu-item">
          <a class="menu-item-link" href="/search">
            
            
              站内搜索
            
          </a>
        </li>
      
    </ul>
  
</nav>

      </header>

      <main id="main" class="main">
        <div class="content-wrapper">
          <div id="content" class="content">
            
  
  <article class="post">
    <header class="post-header">
      <h1 class="post-title">
        
          痛苦的数据结构OJ
        
      </h1>

      <div class="post-meta">
        <span class="post-time">
          2017-05-17
        </span>
        
        
        
      </div>
    </header>

    
    
  <div class="post-toc" id="post-toc">
    <h2 class="post-toc-title">文章目录</h2>
    <div class="post-toc-content">
      <ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#A-B-Problem-II"><span class="toc-text">A - B Problem II</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#陶陶摘苹果"><span class="toc-text">陶陶摘苹果</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#校门外的树"><span class="toc-text">校门外的树</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#自动加密"><span class="toc-text">自动加密</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#计算秒数"><span class="toc-text">计算秒数</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法2-1：集合union"><span class="toc-text">算法2-1：集合union</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法2-2：有序线性表的有序合并"><span class="toc-text">算法2-2：有序线性表的有序合并</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法2-3-2-6：Big-Bang"><span class="toc-text">算法2-3~2-6：Big Bang</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法2-8-2-11：链表的基本操作"><span class="toc-text">算法2-8~2-11：链表的基本操作</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法2-13-2-16：静态链表"><span class="toc-text">算法2-13~2-16：静态链表</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法2-18-2-19：双向循环链表"><span class="toc-text">算法2-18~2-19：双向循环链表</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法2-23：一元多项式加法"><span class="toc-text">算法2-23：一元多项式加法</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#算法3-1：八进制数"><span class="toc-text">算法3-1：八进制数</span></a></li></ol>
    </div>
  </div>


    <div class="post-content">
      
        <p>感觉这篇博客写完，会方便更多同学。。。。 <a id="more"></a><br>有些题目真的，很难啊，最后的几道题目，我也是谷歌的！做到吐血。。</p>
<h2 id="A-B-Problem-II"><a href="#A-B-Problem-II" class="headerlink" title="A - B Problem II"></a>A - B Problem II</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSRz4O.png" alt="oj"></p>
<p>这是个大数相加的问题，即高精度加法<br>贴一发<a href="http://www.51itong.net/acm-4808.html" target="_blank" rel="noopener">高精度模板总结</a></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> L=<span class="number">110</span>;</span><br><span class="line"><span class="function"><span class="built_in">string</span> <span class="title">sub</span><span class="params">(<span class="built_in">string</span> a,<span class="built_in">string</span> b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">string</span> ans;</span><br><span class="line">    <span class="keyword">int</span> na[L]=&#123;<span class="number">0</span>&#125;,nb[L]=&#123;<span class="number">0</span>&#125;;</span><br><span class="line">    <span class="keyword">int</span> la=a.size(),lb=b.size();</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;la;i++) na[la<span class="number">-1</span>-i]=a[i]-<span class="string">'0'</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;lb;i++) nb[lb<span class="number">-1</span>-i]=b[i]-<span class="string">'0'</span>;</span><br><span class="line">    <span class="keyword">int</span> lmax=la&gt;lb?la:lb;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;lmax;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        na[i]-=nb[i];</span><br><span class="line">        <span class="keyword">if</span>(na[i]&lt;<span class="number">0</span>) na[i]+=<span class="number">10</span>,na[i+<span class="number">1</span>]--;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(!na[--lmax]&amp;&amp;lmax&gt;<span class="number">0</span>)  ;lmax++;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=lmax<span class="number">-1</span>;i&gt;=<span class="number">0</span>;i--) ans+=na[i]+<span class="string">'0'</span>;</span><br><span class="line">    <span class="keyword">return</span> ans;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">string</span> a,b;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;a&gt;&gt;b) <span class="built_in">cout</span>&lt;&lt;sub(a,b)&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="陶陶摘苹果"><a href="#陶陶摘苹果" class="headerlink" title="陶陶摘苹果"></a>陶陶摘苹果</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWpCD.png" alt="oj"></p>
<p>这个就注意一下，多组数据测试就行了，没打过ACM的可能会出错<span style="color: red;">while(cin&gt;&gt;a[0])</span></p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta"># <span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> a[<span class="number">10</span>],h;</span><br><span class="line">	<span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;a[<span class="number">0</span>])&#123;</span><br><span class="line">	<span class="keyword">int</span> sum=<span class="number">0</span>;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;<span class="number">10</span>;i++)</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;a[i];</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;h;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">10</span>;i++)&#123;</span><br><span class="line">		<span class="keyword">if</span>(h+<span class="number">30</span>&gt;=a[i])</span><br><span class="line">		sum++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;sum&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="校门外的树"><a href="#校门外的树" class="headerlink" title="校门外的树"></a>校门外的树</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWFKA.png" alt="oj"></p>
<p>这道题是参考洛洛师傅的，其中把要移走的树值赋为<strong>-1</strong>，然后计算值为<strong>-1</strong>的数目<br>个人感觉这个思想很好。。。。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> L,M,a,b,i,move,j;</span><br><span class="line">	<span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;L&gt;&gt;M)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">int</span> s[<span class="number">10001</span>]=&#123;<span class="number">0</span>&#125;;</span><br><span class="line">		<span class="keyword">while</span>(M--)&#123;</span><br><span class="line">			<span class="built_in">cin</span>&gt;&gt;a&gt;&gt;b;</span><br><span class="line">			<span class="keyword">for</span>(i=a;i&lt;=b;i++)</span><br><span class="line">				s[i]=<span class="number">-1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		move=<span class="number">0</span>;</span><br><span class="line">		<span class="keyword">for</span>(j=<span class="number">0</span>;j&lt;=L;j++)&#123;</span><br><span class="line">			<span class="keyword">if</span>(s[j]==<span class="number">-1</span>)</span><br><span class="line">				move+=<span class="number">1</span>;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="built_in">cout</span>&lt;&lt;L-move+<span class="number">1</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="自动加密"><a href="#自动加密" class="headerlink" title="自动加密"></a>自动加密</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWe58.png" alt="oj"></p>
<p>这道题就是注意大小写都要写，然后字符对照ASCII,转换一下就行了<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> i;</span><br><span class="line">	<span class="keyword">char</span> s[<span class="number">100</span>];</span><br><span class="line">	<span class="built_in">cin</span>&gt;&gt;s;</span><br><span class="line">	<span class="keyword">for</span>(i=<span class="number">0</span>;s[i];i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(s[i]&gt;=<span class="string">'a'</span>&amp;&amp;s[i]&lt;=<span class="string">'z'</span>)</span><br><span class="line">		&#123;</span><br><span class="line">			s[i]+=<span class="number">5</span>;</span><br><span class="line">			<span class="keyword">if</span>(s[i]&gt;<span class="string">'z'</span>)</span><br><span class="line">			&#123;</span><br><span class="line">				s[i]-=<span class="number">26</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">		<span class="keyword">else</span> <span class="keyword">if</span>(s[i]&gt;=<span class="string">'A'</span>&amp;&amp;s[i]&lt;=<span class="string">'Z'</span>)&#123;</span><br><span class="line">			s[i]+=<span class="number">5</span>;</span><br><span class="line">			<span class="keyword">if</span>(s[i]&gt;<span class="string">'Z'</span>)</span><br><span class="line">			&#123;</span><br><span class="line">				s[i]-=<span class="number">26</span>;</span><br><span class="line">			&#125;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;s&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="计算秒数"><a href="#计算秒数" class="headerlink" title="计算秒数"></a>计算秒数</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWPvd.png" alt="oj"></p>
<p>这个和上一道题思路差不多，字符转数字<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum</span><span class="params">(<span class="keyword">char</span> x,<span class="keyword">char</span> y,<span class="keyword">int</span> z)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> result;</span><br><span class="line">	<span class="keyword">if</span>(x==<span class="string">'0'</span>)&#123;</span><br><span class="line">		result=(y<span class="number">-48</span>)*z;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span>&#123;</span><br><span class="line">		result=((x<span class="number">-48</span>)*<span class="number">10</span>+y<span class="number">-48</span>)*z;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> result;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> i,n,h,m,s;</span><br><span class="line">	<span class="keyword">char</span> t[<span class="number">10</span>];</span><br><span class="line">	<span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;n)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;n;i++)&#123;</span><br><span class="line">			<span class="built_in">cin</span>&gt;&gt;t;</span><br><span class="line">			h=sum(t[<span class="number">0</span>],t[<span class="number">1</span>],<span class="number">3600</span>);</span><br><span class="line">			m=sum(t[<span class="number">3</span>],t[<span class="number">4</span>],<span class="number">60</span>);</span><br><span class="line">			s=sum(t[<span class="number">6</span>],t[<span class="number">7</span>],<span class="number">1</span>);</span><br><span class="line">			<span class="built_in">cout</span>&lt;&lt;h+m+s&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="算法2-1：集合union"><a href="#算法2-1：集合union" class="headerlink" title="算法2-1：集合union"></a>算法2-1：集合union</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWZUf.png" alt="oj"></p>
<p>这道题给出了合并函数，补充表头，和定义类就行了，注意输出<strong>n+2</strong>行<br><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">List</span>&#123;</span></span><br><span class="line">	<span class="keyword">int</span> L[<span class="number">205</span>];</span><br><span class="line">	<span class="keyword">int</span> length;</span><br><span class="line">&#125;List;</span><br><span class="line">List La,Lb;</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">LocateElem</span><span class="params">(List &amp;La,<span class="keyword">int</span> e)</span></span>&#123;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;La.length;i++)&#123;</span><br><span class="line">		<span class="keyword">if</span>(La.L[i]==e)</span><br><span class="line">			<span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">show</span><span class="params">(List &amp;L)</span></span>&#123;</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;L.L[<span class="number">0</span>];</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;L.length;i++)</span><br><span class="line">		<span class="built_in">cout</span>&lt;&lt;<span class="string">" "</span>&lt;&lt;L.L[i];</span><br><span class="line">	<span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Union</span><span class="params">(List &amp;La,List &amp;Lb)</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> e;</span><br><span class="line">	<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;Lb.length;i++)&#123;</span><br><span class="line">		e=Lb.L[i];</span><br><span class="line">		<span class="keyword">if</span>(!LocateElem(La,e))&#123;</span><br><span class="line">			La.L[La.length]=e;</span><br><span class="line">			La.length++;			</span><br><span class="line">		&#125;</span><br><span class="line">		show(La);</span><br><span class="line">	&#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	<span class="keyword">int</span> n1,n2,i;</span><br><span class="line">	<span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;n1)&#123; </span><br><span class="line">		<span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;n1;i++)</span><br><span class="line">			<span class="built_in">cin</span>&gt;&gt;La.L[i];</span><br><span class="line">		La.length=n1;</span><br><span class="line">		<span class="built_in">cin</span>&gt;&gt;n2;</span><br><span class="line">		<span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;n2;i++)	</span><br><span class="line">			<span class="built_in">cin</span>&gt;&gt;Lb.L[i];</span><br><span class="line">		Lb.length=n2;</span><br><span class="line">		show(La);</span><br><span class="line">		show(Lb);</span><br><span class="line">		Union(La,Lb);</span><br><span class="line">		<span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">	&#125; </span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<h2 id="算法2-2：有序线性表的有序合并"><a href="#算法2-2：有序线性表的有序合并" class="headerlink" title="算法2-2：有序线性表的有序合并"></a>算法2-2：有序线性表的有序合并</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWkDI.png" alt="oj"></p>
<p>上道题会了，这道题就会了，就是变一下主函数,并且注意空格格式，ACM要求很严格</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">List</span>&#123;</span></span><br><span class="line">	<span class="keyword">int</span> date[<span class="number">200</span>];</span><br><span class="line">	<span class="keyword">int</span> length;</span><br><span class="line">&#125;List;</span><br><span class="line">List La,Lb;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">InitList</span><span class="params">(List &amp;L)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    L.length=<span class="number">0</span>;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListLength</span><span class="params">(List L)</span></span>&#123;  </span><br><span class="line">    <span class="keyword">return</span> L.length;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">GetElem</span><span class="params">(List L,<span class="keyword">int</span> p,<span class="keyword">int</span> &amp;e)</span></span>&#123;  </span><br><span class="line">    <span class="keyword">if</span>(p&lt;<span class="number">1</span>||p&gt;L.length)  </span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">    e=L.date[p];  </span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListInsert</span><span class="params">(List &amp;L,<span class="keyword">int</span> p,<span class="keyword">int</span> e)</span></span>&#123;  </span><br><span class="line">    <span class="keyword">int</span> i;  </span><br><span class="line">    <span class="keyword">if</span>(p&lt;<span class="number">1</span>||p&gt;L.length||L.length==<span class="number">200</span><span class="number">-1</span>)  </span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">    <span class="keyword">for</span>(i=L.length;i&gt;=p;--i)  </span><br><span class="line">        L.date[i+<span class="number">1</span>]=L.date[i];  </span><br><span class="line">    L.date[p]=e;  </span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">MergeList</span><span class="params">(List La,List Lb,List &amp;Lc)</span></span>&#123;  </span><br><span class="line">    <span class="keyword">int</span> La_len,Lb_len;  </span><br><span class="line">    <span class="keyword">int</span> ai,bj;  </span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">1</span>,j=<span class="number">1</span>,k=<span class="number">0</span>;  </span><br><span class="line">    InitList(Lc);  </span><br><span class="line">    La_len=ListLength(La);  </span><br><span class="line">    Lb_len=ListLength(Lb);  </span><br><span class="line">    Lc.length=La.length+Lb.length;  </span><br><span class="line">    <span class="keyword">while</span>((i&lt;=La_len)&amp;&amp;(j&lt;=Lb_len))&#123;  </span><br><span class="line">        GetElem(La,i,ai);  </span><br><span class="line">        GetElem(Lb,j,bj);  </span><br><span class="line">        <span class="keyword">if</span>(ai&lt;=bj)&#123;  </span><br><span class="line">            ListInsert(Lc,++k,ai);  </span><br><span class="line">            ++i;  </span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;  </span><br><span class="line">            ListInsert(Lc,++k,bj);  </span><br><span class="line">            ++j;  </span><br><span class="line">        &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">while</span> (i&lt;=La_len)&#123;  </span><br><span class="line">        GetElem(La,i++,ai);  </span><br><span class="line">        ListInsert(Lc,++k,ai);  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">while</span>(j&lt;=Lb_len)&#123;  </span><br><span class="line">        GetElem(Lb,j++,bj);  </span><br><span class="line">        ListInsert(Lc,++k,bj);  </span><br><span class="line">    &#125;     </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">	List La,Lb,Lc;  </span><br><span class="line">    InitList(La);  </span><br><span class="line">    InitList(Lb);  </span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;La.length)&#123;  </span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=La.length;i++)&#123;  </span><br><span class="line">            <span class="built_in">cin</span>&gt;&gt;La.date[i];  </span><br><span class="line">        &#125;  </span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;Lb.length;  </span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i&lt;=Lb.length;i++)&#123;  </span><br><span class="line">            <span class="built_in">cin</span>&gt;&gt;Lb.date[i];  </span><br><span class="line">        &#125;  </span><br><span class="line">        MergeList(La,Lb,Lc);  </span><br><span class="line">        <span class="keyword">if</span>(Lc.length!=<span class="number">0</span>)&#123;  </span><br><span class="line">            <span class="built_in">cout</span>&lt;&lt;Lc.date[<span class="number">1</span>];  </span><br><span class="line">            <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">2</span>;i&lt;=Lc.length;i++)  </span><br><span class="line">                <span class="built_in">cout</span>&lt;&lt;<span class="string">" "</span>&lt;&lt;Lc.date[i];  </span><br><span class="line">        &#125;  </span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;  </span><br><span class="line">    &#125;  </span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="算法2-3-2-6：Big-Bang"><a href="#算法2-3-2-6：Big-Bang" class="headerlink" title="算法2-3~2-6：Big Bang"></a>算法2-3~2-6：Big Bang</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWAbt.png" alt="oj"></p>
<p>这是谷歌加修改的。</p>
<figure class="highlight cs"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#include&lt;stdio.h&gt;</span></span><br><span class="line"><span class="meta">#include&lt;stdlib.h&gt;</span></span><br><span class="line"><span class="meta">#include&lt;string.h&gt;</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> LIST_INIT_SIZE 100</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> LISTINCREMENT 10</span></span><br><span class="line">typedef <span class="keyword">struct</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">char</span> name[<span class="number">100</span>];</span><br><span class="line">&#125;ElemType;</span><br><span class="line">typedef <span class="keyword">struct</span></span><br><span class="line">&#123;</span><br><span class="line">    ElemType * elem;</span><br><span class="line">    <span class="keyword">int</span> length;</span><br><span class="line">    <span class="keyword">int</span> listsize;</span><br><span class="line">&#125;List;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">InitList</span>(<span class="params">List &amp;L</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    L.elem = (ElemType *)malloc(LIST_INIT_SIZE*<span class="keyword">sizeof</span>(ElemType));</span><br><span class="line">    <span class="keyword">if</span>(!L.elem)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    L.length = <span class="number">0</span>;</span><br><span class="line">    L.listsize = LIST_INIT_SIZE;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListInsert</span>(<span class="params">List &amp;L,<span class="keyword">int</span> i,ElemType e</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    ElemType *p;</span><br><span class="line">    <span class="keyword">if</span>(i&lt;<span class="number">1</span>||i&gt;L.length+<span class="number">1</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">if</span>(L.length&gt;=L.listsize)</span><br><span class="line">    &#123;</span><br><span class="line">        ElemType *newbase;</span><br><span class="line">        newbase = (ElemType *)realloc(L.elem,(L.listsize+LISTINCREMENT)*<span class="keyword">sizeof</span>(ElemType));</span><br><span class="line">        <span class="keyword">if</span>(!newbase)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        L.elem = newbase;</span><br><span class="line">        L.listsize+=LISTINCREMENT;</span><br><span class="line">    &#125;</span><br><span class="line">    ElemType *q = &amp;(L.elem[i<span class="number">-1</span>]);</span><br><span class="line">    <span class="keyword">for</span>(p = &amp;(L.elem[L.length<span class="number">-1</span>]);p&gt;=q;--p)</span><br><span class="line">        *(p+<span class="number">1</span>)=*p;</span><br><span class="line">    *q=e;</span><br><span class="line">    ++L.length;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListDlete</span> (<span class="params">List &amp;L,<span class="keyword">int</span> i,ElemType e</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    ElemType *p,*q;</span><br><span class="line">    <span class="keyword">if</span>(i&lt;<span class="number">1</span>||i&gt;L.length)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    p=&amp;(L.elem[i<span class="number">-1</span>]);</span><br><span class="line">    e=*p;</span><br><span class="line">    q=L.elem+L.length<span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span>(++p;p&lt;=q;++p)</span><br><span class="line">    &#123;</span><br><span class="line">        *(p<span class="number">-1</span>)=*p;</span><br><span class="line">    &#125;</span><br><span class="line">    --L.length;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">LocateElem</span>(<span class="params">List L,ElemType e,<span class="keyword">int</span>(*compare</span>)(<span class="params">ElemType,ElemType</span>))</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line">    ElemType *p;</span><br><span class="line">    i=<span class="number">1</span>;</span><br><span class="line">    p=L.elem;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=L.length&amp;&amp;!(*compare)(*p++,e))</span><br><span class="line">        ++i;</span><br><span class="line">    <span class="keyword">if</span>(i&lt;=L.length)</span><br><span class="line">        <span class="keyword">return</span> i;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">listshow</span>(<span class="params">List L</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;L.length;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(i)</span><br><span class="line">            putchar(<span class="string">' '</span>);</span><br><span class="line">        printf(<span class="string">"%s"</span>,L.elem[i].name);</span><br><span class="line">    &#125;</span><br><span class="line">    putchar(<span class="string">'\n'</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">cmp</span>(<span class="params">ElemType e1, ElemType e2</span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">       <span class="keyword">return</span> (<span class="keyword">int</span>)!strcmp(e1.name, e2.name);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span> (<span class="params"><span class="keyword">void</span></span>)</span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">char</span> mark[<span class="number">10</span>];</span><br><span class="line">    List nameList;</span><br><span class="line">    InitList(nameList);</span><br><span class="line">    <span class="keyword">int</span> number;</span><br><span class="line">    ElemType e;</span><br><span class="line">    <span class="keyword">while</span>(~scanf(<span class="string">"%s"</span>,mark))</span><br><span class="line">    &#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">if</span>(strcmp(mark,<span class="string">"insert"</span>)==<span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            scanf(<span class="string">"%d %s"</span>,&amp;number,e.name);</span><br><span class="line">            ListInsert(nameList,number,e);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(strcmp(mark,<span class="string">"show"</span>)==<span class="number">0</span>)</span><br><span class="line">            listshow(nameList);</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(strcmp(mark,<span class="string">"delete"</span>)==<span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            scanf(<span class="string">"%s"</span>,e.name);</span><br><span class="line">            number=LocateElem(nameList,e,cmp);</span><br><span class="line">            ListDlete(nameList,number,e);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(strcmp(mark,<span class="string">"search"</span>)==<span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            scanf(<span class="string">"%s"</span>,e.name);</span><br><span class="line">            printf(<span class="string">"%d\n"</span>,LocateElem(nameList,e,cmp));</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="算法2-8-2-11：链表的基本操作"><a href="#算法2-8-2-11：链表的基本操作" class="headerlink" title="算法2-8~2-11：链表的基本操作"></a>算法2-8~2-11：链表的基本操作</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWCgH.png" alt="oj"></p>
<p>这个也是谷歌加修改的。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;string.h&gt;  </span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;malloc.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdio.h&gt;   </span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;math.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> TRUE 1  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> FALSE 0  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK 1  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR 0  </span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> INFEASIBLE -1</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Status;  </span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Boolean;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> ElemType;</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">LNode</span>  </span></span><br><span class="line"><span class="class">&#123;</span>  </span><br><span class="line">    ElemType data;  </span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">LNode</span> *<span class="title">next</span>;</span>  </span><br><span class="line">&#125;;  </span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">LNode</span> *<span class="title">LinkList</span>;</span>  </span><br><span class="line">  </span><br><span class="line"><span class="function">Status <span class="title">GetElem</span><span class="params">(LinkList L,<span class="keyword">int</span> i,ElemType *e)</span></span></span><br><span class="line"><span class="function"></span>&#123; </span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">1</span>;</span><br><span class="line">    LinkList p=L-&gt;next;</span><br><span class="line">    <span class="keyword">while</span>(p&amp;&amp;j&lt;i) </span><br><span class="line">    &#123;  </span><br><span class="line">        p=p-&gt;next;  </span><br><span class="line">        j++;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">if</span>(!p||j&gt;i)</span><br><span class="line">        <span class="keyword">return</span> ERROR;  </span><br><span class="line">    *e=p-&gt;data; </span><br><span class="line">    <span class="keyword">return</span> OK;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line"><span class="function">Status <span class="title">ListInsert</span><span class="params">(LinkList L,<span class="keyword">int</span> i,ElemType e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">0</span>;  </span><br><span class="line">    LinkList p=L,s;  </span><br><span class="line">    <span class="keyword">while</span>(p&amp;&amp;j&lt;i<span class="number">-1</span>)</span><br><span class="line">    &#123;  </span><br><span class="line">        p=p-&gt;next;  </span><br><span class="line">        j++;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">if</span>(!p||j&gt;i<span class="number">-1</span>) </span><br><span class="line">        <span class="keyword">return</span> ERROR;  </span><br><span class="line">    s=(LinkList)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(struct LNode)); </span><br><span class="line">    s-&gt;data=e;</span><br><span class="line">    s-&gt;next=p-&gt;next;  </span><br><span class="line">    p-&gt;next=s;  </span><br><span class="line">    <span class="keyword">return</span> OK;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function">Status <span class="title">ListDelete</span><span class="params">(LinkList L,<span class="keyword">int</span> i,ElemType *e)</span> </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">0</span>;  </span><br><span class="line">    LinkList p=L,q;  </span><br><span class="line">    <span class="keyword">while</span>(p-&gt;next&amp;&amp;j&lt;i<span class="number">-1</span>)  </span><br><span class="line">    &#123;  </span><br><span class="line">        p=p-&gt;next;  </span><br><span class="line">        j++;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">if</span>(!p-&gt;next||j&gt;i<span class="number">-1</span>)</span><br><span class="line">        <span class="keyword">return</span> ERROR;  </span><br><span class="line">    q=p-&gt;next;  </span><br><span class="line">    p-&gt;next=q-&gt;next;  </span><br><span class="line">    *e=q-&gt;data;  </span><br><span class="line">    <span class="built_in">free</span>(q);  </span><br><span class="line">    <span class="keyword">return</span> OK;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">CreateList</span><span class="params">(LinkList *L,<span class="keyword">int</span> n)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i;  </span><br><span class="line">    LinkList p;  </span><br><span class="line">    *L=(LinkList)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(struct LNode));  </span><br><span class="line">    (*L)-&gt;next=<span class="literal">NULL</span>; </span><br><span class="line">    <span class="keyword">for</span>(i=n; i&gt;<span class="number">0</span>; --i)  </span><br><span class="line">    &#123;  </span><br><span class="line">        p=(LinkList)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(struct LNode)); </span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;p-&gt;data);   </span><br><span class="line">        p-&gt;next=(*L)-&gt;next;</span><br><span class="line">        (*L)-&gt;next=p;  </span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ShowList</span><span class="params">(LinkList L)</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">int</span> numOfList = <span class="number">0</span>; </span><br><span class="line">    LinkList p = L-&gt;next;  </span><br><span class="line">    <span class="keyword">while</span>(p) </span><br><span class="line">    &#123;  </span><br><span class="line">        <span class="keyword">if</span>(numOfList)  </span><br><span class="line">        &#123;  </span><br><span class="line">            <span class="built_in">putchar</span>(<span class="string">' '</span>);  </span><br><span class="line">        &#125;  </span><br><span class="line">        numOfList++; </span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">"%d"</span>,p-&gt;data); </span><br><span class="line">        p = p-&gt;next;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">if</span>(numOfList == <span class="number">0</span>) </span><br><span class="line">    &#123;  </span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">    &#125;  </span><br><span class="line">    <span class="keyword">else</span>  </span><br><span class="line">    &#123;  </span><br><span class="line">        <span class="built_in">putchar</span>(<span class="string">'\n'</span>); </span><br><span class="line">        <span class="keyword">return</span> numOfList;</span><br><span class="line">    &#125;  </span><br><span class="line">&#125;  </span><br><span class="line">  </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span>  </span></span><br><span class="line"><span class="function"></span>&#123;  </span><br><span class="line">    <span class="keyword">int</span> n; </span><br><span class="line">    <span class="keyword">int</span> m;  </span><br><span class="line">    <span class="keyword">char</span> strInst[<span class="number">30</span>]; </span><br><span class="line">    <span class="keyword">int</span> a; </span><br><span class="line">    LinkList L;</span><br><span class="line">    <span class="keyword">int</span> e; </span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n); </span><br><span class="line">    CreateList(&amp;L, n); </span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;m);  </span><br><span class="line">    <span class="keyword">while</span>(m--)</span><br><span class="line">    &#123;  </span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">"%s"</span>, strInst);  </span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">strcmp</span>(strInst, <span class="string">"get"</span>) == <span class="number">0</span>) </span><br><span class="line">        &#123;  </span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;a);  </span><br><span class="line">            <span class="keyword">if</span>(GetElem(L, a, &amp;e) == OK)</span><br><span class="line">            &#123;  </span><br><span class="line">                <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, e); </span><br><span class="line">            &#125;  </span><br><span class="line">            <span class="keyword">else</span> </span><br><span class="line">            &#123;  </span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">"get fail"</span>);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;  </span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">strcmp</span>(strInst, <span class="string">"insert"</span>) == <span class="number">0</span>)  </span><br><span class="line">        &#123;  </span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;a, &amp;e);  </span><br><span class="line">            <span class="keyword">if</span>(ListInsert(L, a, e) == OK)  </span><br><span class="line">            &#123;  </span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">"insert OK"</span>);</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span>  </span><br><span class="line">            &#123;</span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">"insert fail"</span>); </span><br><span class="line">            &#125;  </span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">strcmp</span>(strInst, <span class="string">"delete"</span>) == <span class="number">0</span>)</span><br><span class="line">        &#123;  </span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;a);</span><br><span class="line">            <span class="keyword">if</span>(ListDelete(L, a, &amp;e) == OK) </span><br><span class="line">            &#123;  </span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">"delete OK"</span>);  </span><br><span class="line">            &#125;  </span><br><span class="line">            <span class="keyword">else</span>  </span><br><span class="line">            &#123;  </span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">"delete fail"</span>);</span><br><span class="line">            &#125;  </span><br><span class="line">        &#125;  </span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">strcmp</span>(strInst, <span class="string">"show"</span>) == <span class="number">0</span>) </span><br><span class="line">        &#123;  </span><br><span class="line">            <span class="keyword">if</span>(ShowList(L) == <span class="number">0</span>)</span><br><span class="line">            &#123;  </span><br><span class="line">                <span class="built_in">puts</span>(<span class="string">"Link list is empty"</span>);</span><br><span class="line">            &#125;  </span><br><span class="line">        &#125;  </span><br><span class="line">    &#125;  </span><br><span class="line">  </span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="算法2-13-2-16：静态链表"><a href="#算法2-13-2-16：静态链表" class="headerlink" title="算法2-13~2-16：静态链表"></a>算法2-13~2-16：静态链表</h2><blockquote>
<p>google+alter</p>
</blockquote>
<p><strong>Sample Input</strong><br>show<br>insert 1 ZHAO<br>show<br>insert 2 QIAN<br>show<br>insert 3 SUN<br>show<br>insert 4 LI<br>insert 5 ZHOU<br>insert 6 WU<br>insert 7 ZHENG<br>insert 8 WANG<br>show<br>insert 1 ZHANG<br>show<br>search LI</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXSIZE 11</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">char</span> ElemType[<span class="number">8</span>];</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    ElemType data;</span><br><span class="line">    <span class="keyword">int</span> cur;</span><br><span class="line">&#125; NodeType;</span><br><span class="line">NodeType space[MAXSIZE];</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> elem;</span><br><span class="line">    <span class="keyword">int</span> length;</span><br><span class="line">    <span class="keyword">int</span> listSize;</span><br><span class="line">&#125; SLinkList;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">LocateElem_SL</span><span class="params">(SLinkList&amp; S, ElemType e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line">    i = S.elem;</span><br><span class="line">    <span class="keyword">while</span> (i &amp;&amp; <span class="built_in">strcmp</span>(space[i].data, e))</span><br><span class="line">        i = space[i].cur;</span><br><span class="line">    <span class="keyword">return</span> i;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">InitSpace_SL</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="built_in">memset</span>(space, <span class="number">0</span> ,<span class="keyword">sizeof</span>(space));</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; MAXSIZE - <span class="number">1</span>; ++i)</span><br><span class="line">        space[i].cur = i + <span class="number">1</span>;</span><br><span class="line">    space[MAXSIZE - <span class="number">1</span>].cur = <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Malloc_SL</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i = space[<span class="number">0</span>].cur;</span><br><span class="line">    <span class="keyword">if</span> (i)</span><br><span class="line">        space[<span class="number">0</span>].cur = space[i].cur;</span><br><span class="line">    <span class="keyword">return</span> i;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Free_SL</span><span class="params">(<span class="keyword">int</span> k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    space[k].cur = space[<span class="number">0</span>].cur;</span><br><span class="line">    space[<span class="number">0</span>].cur = k;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Insert_SL</span><span class="params">(SLinkList&amp; S, <span class="keyword">int</span> i, ElemType e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> cur = S.elem;</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> newNodeIndex;</span><br><span class="line">    <span class="keyword">while</span>(j&lt;i<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        cur = space[cur].cur;</span><br><span class="line">        ++j;</span><br><span class="line">    &#125;</span><br><span class="line">    newNodeIndex = Malloc_SL();</span><br><span class="line">    <span class="built_in">strcpy</span>(space[newNodeIndex].data,e);</span><br><span class="line">    space[newNodeIndex].cur = <span class="number">0</span>;</span><br><span class="line">    space[newNodeIndex].cur = space[cur].cur;</span><br><span class="line">    space[cur].cur = newNodeIndex;</span><br><span class="line">    S.length++;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Delete_SL</span><span class="params">(SLinkList&amp; S, <span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> cur = S.elem;</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> delCur;</span><br><span class="line">    <span class="keyword">while</span>(j&lt;i<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        cur = space[cur].cur;</span><br><span class="line">        ++j;</span><br><span class="line">    &#125;</span><br><span class="line">    delCur = space[cur].cur;</span><br><span class="line">    space[cur].cur = space[delCur].cur;</span><br><span class="line">    Free_SL(delCur);</span><br><span class="line">    S.length--;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">CreateList_SL</span><span class="params">(SLinkList&amp; S)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    S.elem = Malloc_SL();</span><br><span class="line">    space[S.elem].cur = <span class="number">0</span>;</span><br><span class="line">    S.length = <span class="number">0</span>;</span><br><span class="line">    S.listSize = <span class="number">9</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Show_space</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">0</span>; i&lt;MAXSIZE; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">"%-8s%2d\n"</span>, space[i].data, space[i].cur);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    SLinkList S;</span><br><span class="line">    <span class="keyword">char</span> str[<span class="number">10</span>];</span><br><span class="line">    <span class="keyword">int</span> a;</span><br><span class="line">    ElemType e;</span><br><span class="line">    InitSpace_SL();</span><br><span class="line">    CreateList_SL(S); </span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">"%s"</span>, str) != EOF)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(<span class="built_in">strcmp</span>(str, <span class="string">"insert"</span>) == <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d%s"</span>, &amp;a, e);</span><br><span class="line">            Insert_SL(S, a, e);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">strcmp</span>(str, <span class="string">"delete"</span>) == <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;a);</span><br><span class="line">            Delete_SL(S, a);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">strcmp</span>(str, <span class="string">"search"</span>) == <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%s"</span>, e);</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">"%2d\n********************\n"</span>, LocateElem_SL(S, e));</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">strcmp</span>(str, <span class="string">"show"</span>) == <span class="number">0</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            Show_space();</span><br><span class="line">            <span class="built_in">puts</span>(<span class="string">"********************"</span>);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="算法2-18-2-19：双向循环链表"><a href="#算法2-18-2-19：双向循环链表" class="headerlink" title="算法2-18~2-19：双向循环链表"></a>算法2-18~2-19：双向循环链表</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWVVP.png" alt="oj"></p>
<blockquote>
<p>google+alter</p>
</blockquote>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">DLNode</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> data;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">DLNode</span> *<span class="title">next</span>;</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">DLNode</span> *<span class="title">prior</span>;</span></span><br><span class="line">&#125; DNLode;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">createDLNode</span><span class="params">(DLNode *&amp;L)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    L = (DLNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(DLNode));</span><br><span class="line">    L-&gt;prior = L;</span><br><span class="line">    L-&gt;next = L;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">printDLNode</span><span class="params">(DLNode *L)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    DLNode *q;</span><br><span class="line">    q=L-&gt;next;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(q!=L)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(i++)<span class="comment">//good idea!</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="built_in">putchar</span>(<span class="string">' '</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">"%d"</span>,q-&gt;data);</span><br><span class="line">        q=q-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insertDLNode</span><span class="params">(DLNode *&amp;L,<span class="keyword">int</span> i,<span class="keyword">int</span> e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    DLNode *q,*qlen;</span><br><span class="line">    q=L;</span><br><span class="line">    qlen=L-&gt;next;</span><br><span class="line">    <span class="keyword">int</span> num=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(qlen!=L)</span><br><span class="line">    &#123;</span><br><span class="line">        num++;</span><br><span class="line">        qlen=qlen-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span>(j&lt;i)</span><br><span class="line">    &#123;</span><br><span class="line">        j++;</span><br><span class="line">        q=q-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(i&gt;num+<span class="number">1</span>||i&lt;<span class="number">1</span>)</span><br><span class="line">       <span class="keyword">return</span> ;</span><br><span class="line">    DLNode *s;</span><br><span class="line">    s=(DLNode *)<span class="built_in">malloc</span> (<span class="keyword">sizeof</span>(DLNode));</span><br><span class="line">    s-&gt;data = e;</span><br><span class="line"></span><br><span class="line">    s-&gt;next = q-&gt;next;</span><br><span class="line">    s-&gt;prior = q;</span><br><span class="line">    q-&gt;next = s;</span><br><span class="line">    q-&gt;next-&gt;prior = s;</span><br><span class="line">    <span class="keyword">return</span> ;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">deleteDLNode</span> <span class="params">(DLNode *&amp;L,<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    DLNode *q,*qlen;</span><br><span class="line">    qlen=L-&gt;next;</span><br><span class="line">    q=L;</span><br><span class="line">    <span class="keyword">int</span> num=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(qlen!=L)</span><br><span class="line">    &#123;</span><br><span class="line">        qlen=qlen-&gt;next;</span><br><span class="line">        num++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(i&lt;<span class="number">1</span>||i&gt;num)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">int</span> j=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(j&lt;i<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        q=q-&gt;next;</span><br><span class="line">        j++;</span><br><span class="line">    &#125;</span><br><span class="line">    DLNode *qfree;</span><br><span class="line">    qfree= q-&gt;next;</span><br><span class="line">    q-&gt;next=qfree-&gt;next;</span><br><span class="line">    qfree-&gt;next-&gt;prior=q;</span><br><span class="line">    <span class="built_in">free</span>(qfree);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span> <span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> n;</span><br><span class="line">    DNLode *L;</span><br><span class="line">    createDLNode(L);</span><br><span class="line">    <span class="keyword">while</span>(~<span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;n))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">switch</span>(n)</span><br><span class="line">        &#123;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">0</span>:</span><br><span class="line">        &#123;</span><br><span class="line">            printDLNode(L);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">1</span>:</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">int</span> i,e;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&amp;i,&amp;e);</span><br><span class="line">            insertDLNode(L,i,e);</span><br><span class="line">           <span class="comment">// printDLNode(L);</span></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">2</span>:</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">int</span> i;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&amp;i);</span><br><span class="line">            deleteDLNode(L,i);</span><br><span class="line">           <span class="comment">// printDLNode(L);</span></span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">default</span>:</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="算法2-23：一元多项式加法"><a href="#算法2-23：一元多项式加法" class="headerlink" title="算法2-23：一元多项式加法"></a>算法2-23：一元多项式加法</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWnPS.png" alt="oj"></p>
<blockquote>
<p>来自洛洛师傅，没有用他给出的函数233333333333333333</p>
</blockquote>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">hs</span><span class="params">(<span class="keyword">char</span>*str,<span class="keyword">int</span> *ss,<span class="keyword">int</span> *sss)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">        <span class="keyword">char</span> *p=<span class="literal">NULL</span>;</span><br><span class="line">        <span class="keyword">int</span> zan;</span><br><span class="line">        zan=atoi(strtok(str,<span class="string">" "</span>));</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> q=<span class="number">0</span>;(p =strtok(<span class="literal">NULL</span>,<span class="string">" "</span>));q++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(q%<span class="number">2</span>==<span class="number">0</span>)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span>(atoi(p)&gt;=<span class="number">0</span>)</span><br><span class="line">                   ss[atoi(p)]=zan;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    sss[<span class="number">-1</span>*atoi(p)]=zan;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">            &#123;</span><br><span class="line">                zan=atoi(p);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">hss</span><span class="params">(<span class="keyword">char</span>*str,<span class="keyword">int</span> *ss,<span class="keyword">int</span> *sss)</span></span></span><br><span class="line"><span class="function"></span>&#123;       <span class="keyword">char</span> *p1=<span class="literal">NULL</span>;</span><br><span class="line">        <span class="keyword">int</span> zan1;</span><br><span class="line">        zan1=atoi(strtok(str,<span class="string">" "</span>));</span><br><span class="line">        <span class="comment">//cout&lt;&lt;zan1&lt;&lt;endl;</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> q=<span class="number">0</span>;(p1 =strtok(<span class="literal">NULL</span>,<span class="string">" "</span>));q++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(q%<span class="number">2</span>==<span class="number">0</span>)</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">if</span>(atoi(p1)&gt;=<span class="number">0</span>)</span><br><span class="line">                   ss[atoi(p1)]+=zan1;</span><br><span class="line">                <span class="keyword">else</span></span><br><span class="line">                    sss[<span class="number">-1</span>*atoi(p1)]+=zan1;</span><br><span class="line">                <span class="comment">//if(ss[atoi(p1)]&gt;0)</span></span><br><span class="line">                <span class="comment">//    ss[atoi(p1)]+=zan1;</span></span><br><span class="line">                <span class="comment">//else</span></span><br><span class="line">                <span class="comment">//  ss[atoi(p1)]=zan1;</span></span><br><span class="line">                <span class="comment">//cout&lt;&lt;ss[atoi(p1)]&lt;&lt;endl;</span></span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span></span><br><span class="line">            &#123;</span><br><span class="line">                zan1=atoi(p1);</span><br><span class="line">                <span class="comment">//cout&lt;&lt;zan1&lt;&lt;endl;</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">&#125;</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">     </span><br><span class="line">    <span class="keyword">char</span> strA[<span class="number">500</span>],strB[<span class="number">500</span>];</span><br><span class="line">    <span class="keyword">while</span>(gets(strA) &amp;&amp; <span class="built_in">strlen</span>(strA))</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">int</span> ss[<span class="number">300</span>]=&#123;<span class="number">0</span>&#125;,sss[<span class="number">300</span>]=&#123;<span class="number">0</span>&#125;;</span><br><span class="line">        hs(strA,ss,sss);</span><br><span class="line">        <span class="keyword">if</span>(gets(strB)&amp;&amp; <span class="built_in">strlen</span>(strB))</span><br><span class="line">            hss(strB,ss,sss);</span><br><span class="line"> </span><br><span class="line">        <span class="keyword">int</span> gg;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">0</span>;j&lt;<span class="number">150</span>;j++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(ss[j]!=<span class="number">0</span>)</span><br><span class="line">                gg=j;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">//gg--;</span></span><br><span class="line">        <span class="keyword">for</span>(;gg&gt;=<span class="number">0</span>;gg--)</span><br><span class="line">          <span class="keyword">if</span>(ss[gg]!=<span class="number">0</span>)</span><br><span class="line">              <span class="built_in">cout</span>&lt;&lt;ss[gg]&lt;&lt;<span class="string">' '</span>&lt;&lt;gg&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">        <span class="keyword">for</span>(<span class="keyword">int</span> y=<span class="number">0</span>;y&lt;<span class="number">300</span>;y++)</span><br><span class="line">            <span class="keyword">if</span>(sss[y]!=<span class="number">0</span>)</span><br><span class="line">                <span class="built_in">cout</span>&lt;&lt;sss[y]&lt;&lt;<span class="string">' '</span>&lt;&lt;<span class="number">-1</span>*y&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="算法3-1：八进制数"><a href="#算法3-1：八进制数" class="headerlink" title="算法3-1：八进制数"></a>算法3-1：八进制数</h2><p><img src="https://s1.ax1x.com/2018/01/01/pSWu8g.png" alt="oj"></p>
<blockquote>
<p>这道题目虽然放在了最后，但是并不难</p>
</blockquote>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;iostream&gt;   </span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stack&gt;   </span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;  </span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAXSIZE 1000    </span></span><br><span class="line"><span class="keyword">char</span> str[MAXSIZE];  </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Conversion</span><span class="params">(<span class="keyword">int</span> num,<span class="keyword">int</span> b)</span></span>&#123;  </span><br><span class="line">    <span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt;S;</span><br><span class="line">    <span class="keyword">do</span>&#123;</span><br><span class="line">        S.push(num%b);  </span><br><span class="line">        num/= b;  </span><br><span class="line">    &#125;<span class="keyword">while</span>(num);</span><br><span class="line">    <span class="keyword">while</span>(!S.empty())&#123;  </span><br><span class="line">        <span class="built_in">cout</span>&lt;&lt;S.top();  </span><br><span class="line">        S.pop();  </span><br><span class="line">    &#125;</span><br><span class="line">   <span class="built_in">cout</span>&lt;&lt;<span class="built_in">endl</span>;  </span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span>  </span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> a,b;  </span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">cin</span>&gt;&gt;a)&#123;  </span><br><span class="line">        b = <span class="number">8</span>; </span><br><span class="line">        Conversion(a,b);  </span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;  </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
      
    </div>

    
      
      



      
      
    

    
      <footer class="post-footer">
        
          <div class="post-tags">
            
              <a href="/tags/c/">c++</a>
            
              <a href="/tags/算法/">算法</a>
            
              <a href="/tags/OJ/">OJ</a>
            
          </div>
        
        
        
  <nav class="post-nav">
    
      <a class="prev" href="/2017/05/18/nodejs反序列化漏洞/">
        <i class="iconfont icon-left"></i>
        <span class="prev-text nav-default">nodejs反序列化漏洞</span>
        <span class="prev-text nav-mobile">上一篇</span>
      </a>
    
    
      <a class="next" href="/2017/05/12/哈希长度扩展攻击/">
        <span class="next-text nav-default">哈希长度扩展攻击</span>
        <span class="prev-text nav-mobile">下一篇</span>
        <i class="iconfont icon-right"></i>
      </a>
    
  </nav>

      </footer>
    

  </article>


          </div>
          
  <div class="comments" id="comments">
      <div id="disqus_thread">
        <noscript>
          Please enable JavaScript to view the
          <a href="//disqus.com/?ref_noscript">comments powered by Disqus.</a>
        </noscript>
      </div> 
    </div>
  </div>


        </div>
      </main>

      <footer id="footer" class="footer">

  <div class="social-links">
    
      
        
          <a href="https://github.com/bay1" class="iconfont icon-github" title="github"></a>
        
      
    
      
        
          <a href="http://weibo.com/3190704711/profile?topnav=1&wvr=6&is_all=1" class="iconfont icon-weibo" title="weibo"></a>
        
      
    
      
    
      
    
      
    
    
    
  </div>


<div class="copyright">
  <span class="copyright-year">
    
    &copy; 
     
      2016 - 
    
    2018
    <span class="author">bay1</span>
  </span>
</div>
      </footer>

      <div class="back-to-top" id="back-to-top">
        <i class="iconfont icon-up"></i>
      </div>
    </div>

    
  
  <script type="text/javascript">
    var disqus_config = function () {
        this.page.url = 'https://bay1.top/2017/05/17/痛苦的数据结构OJ/';
        this.page.identifier = '2017/05/17/痛苦的数据结构OJ/';
        this.page.title = '痛苦的数据结构OJ';
    };
    (function() {
    var d = document, s = d.createElement('script');

    s.src = '//https-blog-flywinky-top-1.disqus.com/embed.js';

    s.setAttribute('data-timestamp', +new Date());
    (d.head || d.body).appendChild(s);
    })();  
  </script>



    
  





  
    <script type="text/javascript" src="/lib/jquery/jquery-3.1.1.min.js"></script>
  

  
    <script type="text/javascript" src="/lib/slideout/slideout.js"></script>
  

  
    <script type="text/javascript" src="/lib/fancybox/jquery.fancybox.pack.js"></script>
  


    <script type="text/javascript" src="/js/src/even.js?v=2.6.0"></script>
<script type="text/javascript" src="/js/src/bootstrap.js?v=2.6.0"></script>
<script src="/js/prettify.js"></script>
<script type="text/javascript">
$(document).ready(function(){
 $('pre').addClass('prettyprint');
   prettyPrint();
 })
</script>
  </body>
</html>
